10261 - Ferry loading/10261.cpp

   1 #include <iostream>
   2 #include <algorithm>
   3 #include <climits>
   4 #include <vector>
   5
   6 using namespace std;
   7
   8 int capacity, n;
   9 vector<int> w;
  10
  11 int dp(int p, int s, int i){
  12   if (i >= n)
  13     return 0;
  14
  15   int ans = -100000;
  16   if (p + w[i] <= capacity) ans = max(ans, dp(p + w[i], s, i+1) + 1);
  17   if (s + w[i] <= capacity) ans = max(ans, dp(p, s + w[i], i+1) + 1);
  18
  19   //cout << p << " " << s << " " << i << " ";
  20   //cout << ans << endl;
  21
  22   return ans;
  23 }
  24
  25 int main(){
  26   int C;
  27   cin >> C;
  28   while (C--){
  29     cin >> capacity;
  30     capacity *= 100;
  31
  32     w.clear();
  33     int x;
  34     while(cin >> x && x){
  35       w.push_back(x);
  36     }
  37
  38     n = w.size();
  39
  40     cout << dp(0,0,0) << endl;
  41   }
  42   return 0;
  43 }